package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LetterCombinations {

    public static void main(String[] args) {

    }
    public  List<String> letterCombinations(String digits) {
        //结果
        List<String> result = new ArrayList<>();
        if (digits.length() == 0) return result;
        StringBuilder stringBuilder = new StringBuilder();

        Map<Character, String> map = new HashMap<>();
        map.put('2',"abc");
        map.put('3',"def");
        map.put('4',"ghi");
        map.put('5',"jkl");
        map.put('6',"mno");
        map.put('7',"pqrs");
        map.put('8',"tuv");
        map.put('9',"wxyz");
        backtrack(digits,0,stringBuilder,result,map);
        return result;
    }
    public void backtrack(String digits,int index,StringBuilder stringBuilder,List<String> result,Map<Character, String> map){

        if (index == digits.length()){
            result.add(stringBuilder.toString());
        }else {
            String s = map.get(digits.charAt(index));
            for (int i = 0; i < s.length(); i++) {
                stringBuilder.append(s.charAt(i));
                backtrack(digits,index + 1,stringBuilder,result,map);
                stringBuilder.deleteCharAt(index);
            }
        }
    }
}
